/*
 * Copyright (c) 2007, Nathan Sturtevant
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the University of Alberta nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY NATHAN STURTEVANT ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.googlecode.pathmachine.mm;

import java.util.ArrayList;
import java.util.List;
import java.util.logging.Logger;

/**
 * Pathfinding with Minimal Sector Abstraction
 * 
 * @author Nathan Sturtevant
 * @author <a href="mailto:eriq.adams@gmail.com">Eriq Muhammad Adams J.</a>
 */
public class MinimalSectorSearch {

    private static final Logger logger = Logger.getLogger(MinimalSectorSearch.class.getName());
    private Map m;

    public MinimalSectorSearch(Map map) {
        this.m = map;
    }

    /**
     * doMinimalPath()
     *
     * Find the minimal path between two x/y locations
     *
     * First an abstract path is computed, and then the low-level path
     * is computed. This is compared to the number of nodes expanded just
     * using A*. The paths are returned by reference so they can be drawn
     * on the screen.
     *
     * Note that we don't move the region center temporarily as described
     * in the AI wisdom book, although that code is running in Dragon Age.
     */
    public List<Integer> doMinimalPath(int startX, int startY,
            int goalX, int goalY,
            MinimalSectorAbstraction ms,
            List<Integer> abstractPath,
            List<Integer> realPath) {
        List<Integer> gAStarPath = new ArrayList<Integer>();
        if (startX < 0 || startX >= m.getMapWidth() || goalX < 0 || goalX >= m.getMapWidth()
                || startY < 0 || startY >= m.getMapHeight() || goalY < 0 || goalY >= m.getMapHeight()) {
            return gAStarPath;
        }
        if ((startX == GenericAStar.UINT32_MAX) || (startY == GenericAStar.UINT32_MAX)
                || (goalX == GenericAStar.UINT32_MAX) || (goalY == GenericAStar.UINT32_MAX)) {
            return gAStarPath;
        }

        MinimalSearchEnvironment mmse = new MinimalSearchEnvironment(ms);
        MapSearchEnvironment mse = new MapSearchEnvironment(m);
        GenericAStar gas = new GenericAStar();
        int concNodes, absNodes, totalNodes;
        concNodes = absNodes = 0;
        totalNodes = 0;

        int x1 = startX;
        int y1 = startY;
        int x2 = goalX;
        int y2 = goalY;

        // find parent sector/region
        int region1 = ms.getRegion(x1, y1);
        int sector1 = ms.getSector(x1, y1);
        int region2 = ms.getRegion(x2, y2);
        int sector2 = ms.getSector(x2, y2);
        if ((region1 == -1) || (sector1 == -1)
                || (region2 == -1) || (sector2 == -1)) {
            return gAStarPath;
        }

        // get abstract path
        gas.getPath(mmse,
                ((int) (sector1 << 16)) | region1,
                ((int) (sector2 << 16)) | region2, abstractPath);
        absNodes = (int) gas.getNodesExpanded();
        totalNodes = absNodes;

        logger.info("Abstract path from [" + sector1 + ":" + region1 + "] to [" + sector2 + ":" + region2 + "]," + absNodes + " nodes expanded");
        logger.info("Abstract path length " + (int) abstractPath.size());

        // replace sector/region with x/y location
        // this if for global drawing later
        for (int x = (int) abstractPath.size() - 1; x >= 0; x--) {
            Point2D p = ms.getXYLocation(abstractPath.get(x) >> 16,
                    abstractPath.get(x) & 0xFFFF);
            int ax = p.x, ay = p.y;
            abstractPath.set(x, ((ax << 16) | ay));
        }

        // if we can't find an abstract path, there won't be a concrete one
        // but we might not have an abstract path if the start/end sector/region
        // are the same
        if ((abstractPath.size() > 0)
                || ((sector1 == sector2) && (region1 == region2))) {
            // start at first abstract center, which we'll promptly skip
            int s = (int) abstractPath.size() - 1;
            List<Integer> concretePath;

            do {
                concretePath = new ArrayList<Integer>();
                s -= 1;
                if (s < 1) {
                    s = 0;
                }
                if ((s > 0) && (s < (int) abstractPath.size())) {
                    x2 = abstractPath.get(s) >> 16;
                    y2 = abstractPath.get(s) & 0xFFFF;
                } else {
                    x2 = goalX;
                    y2 = goalY;
                }

                gas.getPath(mse, (x1 << 16) | y1, (x2 << 16) | y2, concretePath);
//            printf("Computing segment from (%d, %d) to (%d, %d): %ld nodes expanded\n",
//                   x1, y1, x2, y2, gas.GetNodesExpanded());
                concNodes = concNodes > (int) gas.getNodesExpanded() ? concNodes : (int) gas.getNodesExpanded();
                totalNodes += gas.getNodesExpanded();

                if (concretePath.isEmpty()) {
                    break;
                }
                for (int cnt = (int) concretePath.size() - 1; cnt >= 0; cnt--) {
                    if ((realPath.isEmpty())
                            || (realPath.get(realPath.size() - 1) != concretePath.get(cnt))) {
                        realPath.add(concretePath.get(cnt));
                    }
                }
                int lasIdx = realPath.size() - 1;
                x1 = realPath.get(lasIdx) >> 16;
                y1 = realPath.get(lasIdx) & 0xFFFF;
            } while (s != 0);

            logger.info("Complete (real) path length " + realPath.size());
            logger.info("Total nodes expanded: " + totalNodes);
        }

        gAStarPath = new ArrayList<Integer>();
        gas.getPath(mse, (startX << 16) | startY, (goalX << 16) | goalY, gAStarPath);
        logger.info("AStar nodes:" + gas.getNodesExpanded() + ", length "
                + gAStarPath.size());

//        char line[256];
//    sprintf(line, "Abstraction: %d nodes, AStar: %ld nodes",
//                totalNodes, gas.GetNodesExpanded());
//        to.AppendToLine(line);

        return gAStarPath;

    }
}
